package JavaStudy.SortUtil;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StopWatch;

import javax.rmi.CORBA.Util;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveAction;

/**
 * @author welsir
 */
@Slf4j
public class QuickSortTask extends RecursiveAction {

    private int[] array;
    private int left;
    private int right;

    public QuickSortTask(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
        int pivot = partition(array, left, right);
        QuickSortTask task1 = null;
        QuickSortTask task2 = null;
        if (pivot - left > 1) {
            task1 = new QuickSortTask(array, left, pivot-1);
            task1.fork();
        }
        if (right - pivot > 1) {
            task2 = new QuickSortTask(array, pivot+1, right);
            task2.fork();
        }
        if (task1 != null && !task1.isDone()) {
            task1.join();
        }
        if (task2 != null && !task2.isDone()) {
            task2.join();
        }
    }

    public static int partition(int[] a, int left, int right) {
        int midle = a[left];
        while (left < right) {
            while (left < right && a[right] >= midle) {
                right--;
            }
            swap(a, left, right);
            while (left < right && a[left] <= midle) {
                left++;
            }
            swap(a, left, right);
        }
        return left;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) throws IllegalAccessException {
        int count = 10000000;
        int[] aa = new int[count];
        int[] bb = new int[count];
        Random random = new Random();
        for (int i = 0; i < aa.length; i++) {
            aa[i] = random.nextInt(count)+1;
            bb[i] = aa[i];
        }
        long startTime = System.currentTimeMillis();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        QuickSortTask task = new QuickSortTask(aa, 0, aa.length-1);
        Future<Void> result = forkJoinPool.submit(task);
        try {
            result.get();
            log.debug("耗时：" + (System.currentTimeMillis() - startTime) + "ms");
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        startTime = System.currentTimeMillis();
        Arrays.sort(bb);
        log.debug("耗时：" + (System.currentTimeMillis() - startTime) + "ms");
    }
}